package jiparada;
import java.util.Vector;
import java.util.LinkedList;
import java.util.Hashtable;
import java.util.TreeSet;

import java.util.Collections;

import java.util.Comparator;

public class PathSolver {

	static char[][] mapArray; //an array to store the map
	static Hashtable<Node,Node> closedSet; //a hashtable for visited nodes
	static Hashtable<String,Node> openSet; //a hashtable for visited nodes
	static Hashtable<String, Node> visited =new Hashtable<String,Node>();;
	static int leftLimit;
	static int rightLimit;
	static int upLimit;
	static int downLimit;
	static int defaultRange =10;
	static int range = defaultRange;
	static int hola = 1;

	/**
	 * Creates the solution (shorest path), by starting with the goal and reversing the solution tree
	 * @param node the goal node
	 * @return a Vector<point> holding the solution to the map
	 */

	private static Vector<Node> constructPath(Node node)
	{
		Vector<Node> solution = new Vector<Node>(1); //a vector to store the solution

		solution.add(node); //we add the last node (goal)

		Node parent = node.getParent(); //we get the parent of the goal

		while(parent!=null) //while we have parents
		{
			solution.add(parent); //we add them to the solution
			parent = parent.getParent();
		}
		range = defaultRange;

		return solution;
	}
	
	public static void setVisited(Node nodo)
	{
		visited.put(nodo.x+","+nodo.y, nodo);
	}


	/**
	 * Builds the solution tree 
	 * @param startNode the starting position
	 * @param goalNode the goal position
	 * @param mapathe the map
	 * @return a Vector<point> holding the solution to the map
	 */

	public static Vector<Node> search(Node startNode, PositionJiparada goalNode,char[][] mapa) 
	{
		if(hola==38)
			System.out.println("cock");
		
		hola++;
		mapArray = mapa; //Guardamos el mapa en un arreglo
		closedSet = new Hashtable<Node,Node>(); // y un hashtable para los lugares visitados.
		openSet = new Hashtable<String,Node>(); // y un hashtable para los lugares abiertos
		Vector<Node> openList = new Vector<Node>();
		boolean tentativeIsBetter;
		double tentative_g_score;
			
		if(startNode.x<=goalNode.x)
		{
			leftLimit = startNode.x-range;
			rightLimit = goalNode.x+range;
		}
		else 
		{
			leftLimit = goalNode.x-range;	
			rightLimit = startNode.x+range;		
		}
		if(startNode.y<=goalNode.y)
		{
			upLimit = startNode.y-range;
			downLimit = goalNode.y+range;
		}
		else 
		{
			upLimit = goalNode.y-range;	
			downLimit = startNode.y+range;		
		}
		if(upLimit<0)
			upLimit=0;
		if(downLimit>mapArray.length)
		{
			downLimit = mapArray.length;
		}
		if(leftLimit<0)
		{
			leftLimit=0;
		}
		if(rightLimit>mapArray[0].length)
		{
			rightLimit= mapArray[0].length;
		}

		openList.add(startNode); //se agrega la posición de partida		
		startNode.setParent(null);
		startNode.g_score = 0;
		startNode.h_score = startNode.calculateDistance(goalNode);

		while (!openList.isEmpty()) //Mientras hay nodos por buscar
		{	
			Collections.sort(openList);
			Node node = openList.remove(0); //removemos el primer nodo.
			closedSet.put(node, node);
			 
			//System.out.println(node.getFScore());
			
			
			/*for(int j=0;j<openList.size();j++)
				System.out.println(openList.get(j).getFScore());
			
			System.out.println("---------------------------------");*/
			
			

			if (node.equals(goalNode) ) //si el nodo actual es el goal
			{
				return constructPath(node); //retornamos el camino
			}

			Vector<Node> neighbors=getNeighbors(node); // lista de vecinos

			for(int i=0;i<neighbors.size();i++)  // para todos los vecinos
			{
				Node neighborNode = neighbors.get(i); //obtenemos el vecino i
				if(neighborNode==null)
					break;
				
				if(closedSet.contains(neighborNode)) // si el vecino ya estaba saltamos al siguiente vecino
					continue;
				
				if(mapArray[neighborNode.y][neighborNode.x]=='#')
				{
					closedSet.put(neighborNode, neighborNode);
					continue;
				}

				tentative_g_score = node.g_score + node.calculateDistance(neighborNode); 

				if(!openSet.contains(neighborNode)) // si el vecino no se encuentra entre los abiertos
				{					
					openSet.put(neighborNode.x+","+neighborNode.y, neighborNode);
					openList.add(neighborNode); //lo agregamos a los abiertos
					tentativeIsBetter = true;		
					
				}else if(openSet.get(neighborNode.x+","+neighborNode.y).g_score>tentative_g_score)
				{
					neighborNode = openSet.get(neighborNode.x+","+neighborNode.y);
					tentativeIsBetter = true;
				}else
					tentativeIsBetter = false;
				
				if(tentativeIsBetter)
				{
					neighborNode.g_score = tentative_g_score;//node.g_score+1; //hacemos update del costo
					neighborNode.h_score = neighborNode.calculateDistance(goalNode); // y de la heurística
					if(visited.contains(neighborNode))
						neighborNode.h_score = neighborNode.h_score+100;
					
					neighborNode.setParent(node); // y el padre es el nodo actual.	
				}
			}
		}

		// no path found
		range+=10;
		
		return null;
	}

	/**
	 * returns the negihbors of a given point
	 * @param position the point whose neighbors are to be calculated
	 * @return a Vector<point> holding the neighbors of the given point
	 */

	private static Vector<Node> getNeighbors(Node position)
	{
		Vector<Node> neighbors = new Vector<Node>(); //a vector for the points

		for(int i=-1;i<2;i++) //we iterate through the eight possible directions
		{
			for(int j=-1;j<2;j++)
			{

				Node auxiliar=new Node(position.x+i,position.y+j); //an auxiliar point to use in the needed direction (up, left, down, right and diagonals)

				if(!(auxiliar.y<upLimit||auxiliar.y>=downLimit||auxiliar.x<leftLimit||auxiliar.x>=rightLimit))
						if(mapArray[auxiliar.y][auxiliar.x]!='#')//we check that they are feasible
							neighbors.add(auxiliar);

			}
		}
		return neighbors; //return them
	}
}
